// 买卖股票的最佳时机III
class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        int INF = -0x3f3f3f3f;
        // 1、建表
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, INF));
        auto g(f);
        // 2、初始化
        f[0][0] = -prices[0];
        g[0][0] = 0;
        // 3、填表
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < 3; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                if(j - 1 < 0)
                    g[i][j] = g[i - 1][j];
                else
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        // 4、返回值
        int ret = INF;
        for(int j = 0; j < 3; ++j)
        {
            ret = max(ret, g[n - 1][j]);
        }
        return ret;
    }
};

// 买卖股票的最佳时机IV
class Solution
{
public:
    const int INF = -0x3f3f3f3f;
    int maxProfit(int k, vector<int>& prices)
    {
        // 1、建表
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, INF));
        auto g(f);
        // 2、初始化
        f[0][0] = -prices[0];
        g[0][0] = 0;
        // 3、填表
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < k + 1; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                if(j - 1 < 0)
                    g[i][j] = g[i - 1][j];
                else
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        // 4、返回值
        int ret = INF;
        for(int j = 0; j < k + 1; ++j)
        {
            ret = max(ret, g[n - 1][j]);
        }
        return ret;
    }
};

// 最大子数组和
class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        // 1、建表
        int n = nums.size();
        vector<int> dp(n + 1);
        // 2、初始化
        dp[0] = 0;
        // 3、填表
        for(int i = 1; i < n + 1; ++i)
        {
            dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
        }
        // 4、返回值
        return *max_element(dp.begin() + 1, dp.end());
    }
};

// 环形子数组的最大和
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums)
    {
        // 1、建表
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        // 2、初始化
        f[0] = g[0] = 0;
        // 3、填表
        int sum = 0;
        for(int i = 1; i < n + 1; ++i)
        {
            sum += nums[i - 1];
            f[i] = max(nums[i - 1], f[i - 1] + nums[i - 1]);
            g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);
        }
        // 4、返回值
        int gMax = *max_element(f.begin() + 1, f.end());
        int gMin = *min_element(g.begin() + 1, g.end());
        if(sum == gMin)
            return gMax;
        else
            return max(gMax, sum - gMin);
    }
};

// 乘积最大子数组
class Solution
{
public:
    int maxProduct(vector<int>& nums)
    {
        // 1、建表
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        // 2、初始化
        f[0] = g[0] = 1;
        // 3、填表
        for(int i = 1; i < n + 1; ++i)
        {
            f[i] = max(nums[i - 1], max(g[i - 1] * nums[i - 1], f[i - 1] * nums[i - 1]));
            g[i] = min(nums[i - 1], min(g[i - 1] * nums[i - 1], f[i - 1] * nums[i - 1]));
        }
        // 4、返回值
        return *max_element(f.begin() + 1, f.end());
    }
};
